import java.util.*;


public class Solution2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        // write code here
        //要么从第一家开始偷，最后一家不能偷，
        //要么从第二家开始偷，最后一家可以偷
        if(nums.length == 1) {
            return nums[0];
        } else if(nums.length == 2) {
            return Math.max(nums[0],nums[1]);
        } else {
            int n = nums.length;
            int[] dp1 = new int[n];
            //偷第一家
            dp1[0] = nums[0];
            for(int i = 1;i<n-1;i++) {
                if(i == 1) {
                    dp1[i] = dp1[i-1];
                }else if(n == 2) {
                    dp1[i] = nums[i] + dp1[0]; 
                } else {
                    dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i]);
                }
            }
            dp1[n-1] = dp1[n-2];
            //不偷第一家
            int[] dp2 = new int[n];
            dp2[0] = 0;
            for(int i = 1;i<n;i++) {
                if(i == 1) {
                    dp2[i] = nums[i];
                } else {
                    dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i]);
                }
            }
            return Math.max(dp1[n-1],dp2[n-1]);
        }
    }
}